package com.cty.nineteenthDay;

import java.util.HashMap;
import java.util.HashSet;

/*
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 *
 * */
public class Q_25 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
//        ListNode listNode2 = new ListNode(2);
//        ListNode listNode3 = new ListNode(0);
//        ListNode listNode4 = new ListNode(-4);
//        listNode1.next = listNode2;
//        listNode2.next = listNode1;
//        listNode3.next = listNode4;
//        listNode4.next = listNode2;
        boolean res = hasCycle(listNode1);
        System.out.println(res);
    }

    // 作者自己写的 超出时间限制 时间复杂度O(n) 空间复杂度O(n)
    public static boolean hasCycle(ListNode head) {
        if (head == null) return false;
        HashMap<Integer, ListNode> map = new HashMap<>();
        ListNode temp = head;
        map.put(temp.val, temp);
        while (temp.next != null) {
            if (map.containsKey(temp.next.val) && map.get(temp.next.val) == temp.next) {
                return true;
            }
            temp = temp.next;
            map.put(temp.val, temp);
        }
        return false;
    }

    // 力扣官方题解 方法一:哈希表
    /*
    * 思路: 利用HashSet.add() 这个方法
    *     HashSet不能出现同一个元素或者对向
    *     add这个方法 如果加入了同一个对象会返回false 如果不存在同一个对象则返回true
    *     时间复杂度O(n) 空间复杂度O(n)
    * */
    public static boolean hasCycle2(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }


    // 力扣官方题解 方法二:快慢指针
    /*
    *  思路: 定义两个指针 一个慢指针 一个快指针
    *       如果存在环 快指针的速度是慢指速度的两倍
    *       总会在某一个节点相遇 相遇即代表有环
    *
    * */
    public static boolean hasCycle3(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast =fast.next.next;
        }
        return true;
    }
}

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
